package com.yusong.algorithm.dp;


import java.util.Arrays;

/**
 * 回溯法
 * 执行时间过长
 */
public class CoinChange {


    /**
     * 状态转移公式：
     * 不能等于-1
     * f(0,amount） = min{ f(1), f(1,amount-x) +1  ,   f(1,amount-2x) +2     }
     */
    public int coinChange(int[] coins, int amount) {
        if(null == coins || coins.length == 0 || amount <0){
            return -1;
        }
        int length = coins.length;

        Arrays.sort(coins);

        int min = eager(coins, amount);

        int[][] cache = new int[length][amount+1];

        int min2 = put(coins, 0, amount, length, cache, min);

        if(min2 >0){
            return min2;
        }
        if(min < Integer.MAX_VALUE){
            return min;
        }

        return -1;
    }

    private int eager(int[] coins, int amount) {
        int sum = 0;
        for(int i = (coins.length -1); i >=0; i--){
            int currentNum = coins[i];
            if(amount%currentNum == 0){
                sum += amount/currentNum;
                return sum;
            }
            if(currentNum > amount){
                continue;
            }
            sum += amount/currentNum;
            amount = amount%currentNum;

        }
        return Integer.MAX_VALUE;
    }

    /**
     * 返回-1 说明找不到方案
     */
    private int put(int[] coins, int index, int balance, int length, int[][] cache,int maxTime){
        if(balance == 0){
            return 0;
        }
        if(index >= length){
            return -1;
        }
        int currentValue = coins[index];

        if(0 != cache[index][balance]){
            return cache[index][balance];
        }

        int times = balance/currentValue;

        int result = Integer.MAX_VALUE;
        boolean find = false;
        for(int i = 0; i <= times; i++){
            int nextBalance = balance - i*currentValue;
            if(nextBalance < 0){
                break;
            }
            if(i > maxTime)
                break;

            int nextResult = put(coins, index+1, nextBalance, length, cache, maxTime - i);

            if(nextResult >= 0){
                find = true;
                if(result > (nextResult +i) ){
                    result = nextResult +i ;
                }
                //System.out.println(index+ " | "+currentValue+ " | "+ i +" | "+ balance + " | " +result);
            }else {
                //System.out.println(index+ " | "+currentValue+ " | "+ i +" | "+ balance + " | 无解" );
            }

        }


        if(!find){
            cache[index][balance] = -1;
            return -1;
        }
        cache[index][balance] = result;
        return result;
    }



    public static void main(String[] args) {
        CoinChange coinChange = new CoinChange();

        int[] data = {1,2,5,10};
        int amount = 18;

        System.out.println(coinChange.coinChange(data, amount));
    }

}



/**

 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

 你可以认为每种硬币的数量是无限的。

  

 示例 1：

 输入：coins = [1, 2, 5], amount = 11
 输出：3
 解释：11 = 5 + 5 + 1

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/coin-change
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


 [474,83,404,3]
 264
 --
 8
 */